#define _CRT_SECURE_NO_WARNINGS 1


//typedef char BTDataType;
//
//typedef struct BinaryTreeNode
//{
//	BTDataType _data;
//	struct BinaryTreeNode* _left;
//	struct BinaryTreeNode* _right;
//}BTNode;
//
//#include "Queue.h"
//
//// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
//BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
//{
//	if ('#' == a[*pi])
//	{
//		(*pi)++;
//		return NULL;
//	}
//
//	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
//	root->_data = a[(*pi)++];
//	root->_left = BinaryTreeCreate(a, n, pi);
//	root->_right = BinaryTreeCreate(a, n, pi);
//
//	return root;
//}
//
//// 二叉树销毁
//void BinaryTreeDestory(BTNode** root)
//{
//	if (NULL == *root)
//	{
//		return;
//	}
//
//	BinaryTreeDestory(&(*root)->_left);
//	BinaryTreeDestory(&(*root)->_right);
//	free(*root);
//	*root = NULL;
//}
//
//// 二叉树节点个数
//int BinaryTreeSize(BTNode* root)
//{
//	return NULL == root ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
//}
//
//// 二叉树叶子节点个数
//int BinaryTreeLeafSize(BTNode* root)
//{
//	if (NULL == root)
//	{
//		return 0;
//	}
//
//	if (NULL == root->_left && NULL == root->_right)
//	{
//		return 1;
//	}
//
//	return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
//}
//
//// 二叉树第k层节点个数
//int BinaryTreeLevelKSize(BTNode* root, int k)
//{
//	assert(k > 0);
//
//	if (NULL == root)
//	{
//		return 0;
//	}
//
//	if (1 == k)
//	{
//		return 1;
//	}
//
//	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
//}
//
//// 二叉树查找值为x的节点
//BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
//{
//	if (NULL == root)
//	{
//		return NULL;
//	}
//
//	if (root->_data == x)
//	{
//		return root;
//	}
//
//	BTNode* left = BinaryTreeFind(root->_left, x);
//
//	if (left)
//	{
//		return left;
//	}
//	else
//	{
//		return BinaryTreeFind(root->_right, x);
//	}
//}
//
//// 二叉树前序遍历
//void BinaryTreePrevOrder(BTNode* root)
//{
//	if (NULL == root)
//	{
//		printf("N ");
//		return;
//	}
//
//	printf("%c ", root->_data);
//	BinaryTreePrevOrder(root->_left);
//	BinaryTreePrevOrder(root->_right);
//}
//
//// 二叉树中序遍历
//void BinaryTreeInOrder(BTNode* root)
//{
//	if (NULL == root)
//	{
//		printf("N ");
//		return;
//	}
//
//	BinaryTreeInOrder(root->_left);
//	printf("%c ", root->_data);
//	BinaryTreeInOrder(root->_right);
//}
//
//// 二叉树后序遍历
//void BinaryTreePostOrder(BTNode* root)
//{
//	if (NULL == root)
//	{
//		printf("N ");
//		return;
//	}
//
//	BinaryTreePostOrder(root->_left);
//	BinaryTreePostOrder(root->_right);
//	printf("%c ", root->_data);
//}
//
//// 层序遍历
//void BinaryTreeLevelOrder(BTNode* root)
//{
//	Queue q;
//	QueueInit(&q);
//
//	if (root)
//	{
//		QueuePush(&q, root);
//	}
//
//	while (!QueueEmpty(&q))
//	{
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//
//		if (front)
//		{
//			printf("%c ", front->_data);
//			QueuePush(&q, front->_left);
//			QueuePush(&q, front->_right);
//		}
//		else
//		{
//			printf("N ");
//		}
//	}
//
//	printf("\n");
//	QueueDestroy(&q);
//}
//
//// 判断二叉树是否是完全二叉树
//bool BinaryTreeComplete(BTNode* root)
//{
//	Queue q;
//	QueueInit(&q);
//
//	if (root)
//	{
//		QueuePush(&q, root);
//	}
//
//	while (!QueueEmpty(&q))
//	{
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//
//		if (NULL == front)
//		{
//			break;
//		}
//
//		QueuePush(&q, front->_left);
//		QueuePush(&q, front->_right);
//	}
//
//	while (!QueueEmpty(&q))
//	{
//		BTNode* front = QueueFront(&q);
//		QueuePop(&q);
//
//		if (front)
//		{
//			QueueDestroy(&q);
//			return false;
//		}
//	}
//
//	QueueDestroy(&q);
//	return true;
//}
//
//
//int main()
//{
//	char a[] = "ABD##E#H##CF##G##";
//	int i = 0;
//	BTNode* root = BinaryTreeCreate(a, sizeof(a) / sizeof(char), &i);
//	//printf("%d\n", BinaryTreeSize(root));
//	//printf("%d\n", BinaryTreeLeafSize(root));
//	//printf("%d\n", BinaryTreeLevelKSize(root, 4));
//	//printf("%c\n", BinaryTreeFind(root, 'F')->_data);
//	//BinaryTreePrevOrder(root);
//	//BinaryTreeInOrder(root);
//	//BinaryTreePostOrder(root);
//	//BinaryTreeLevelOrder(root);
//
//	if (BinaryTreeComplete(root))
//	{
//		printf("true");
//	}
//	else
//	{
//		printf("false");
//	}
//
//	BinaryTreeDestory(&root);
//
//	return 0;
//}


//bool isSameTree(struct TreeNode* p, struct TreeNode* q)
//{
//	if (NULL == p && NULL == q)
//	{
//		return true;
//	}
//
//	if (NULL == p || NULL == q)
//	{
//		return false;
//	}
//
//	if (p->val != q->val)
//	{
//		return false;
//	}
//
//	return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//}


bool _isSymmetric(struct TreeNode* root1, struct TreeNode* root2)
{
	if (NULL == root1 && NULL == root2)
	{
		return true;
	}

	if (NULL == root1 || NULL == root2)
	{
		return false;
	}

	if (root1->val != root2->val)
	{
		return false;
	}

	return _isSymmetric(root1->left, root2->right) && _isSymmetric(root1->right, root2->left);
}

bool isSymmetric(struct TreeNode* root)
{
	return _isSymmetric(root->left, root->right);
}